1. Field of the Invention
This invention relates to devices and processes for encoding digitized information using vector quantization.
2. Description of Related Art
Hashing is a database technique which organizes records of a database into indexed "buckets" and uses a hashing function to identify the bucket containing a desired record. The hashing function has an input called a key which depends on a record being sought and an output which is an index. The index indicates the location (i.e. starting address) of a bucket containing the desired record. The bucket indicated by the index is searched to find the desired record.
An example of a hashing-based database is a set of customer records for a cash machine, where each record has a unique 19-digit card number. To find a customer's record, an exhaustive search can be made through the database until a record containing the card number is found. This typically results in an unreasonably long search time. Alternatively, a directory to the database could contain pointers to individual records indexed by 19-digit card numbers, but the directory would greatly increase the size of the database. An alternative is to apply a hashing function to the 19-digit card number to generate an index within a range smaller than the range of the card number. The hashing function could, for example, be a mask which preserves the five least significant digits of the card number. Since the range of the hashing function is smaller than the range of the card number, more than one customer record may hash to the same index. When this happens, the index indicates a bucket containing more than one record. The bucket is searched for the desired record, but searching the bucket takes considerably less time than searching the entire database. Additionally, the amount of memory required to implement the hashing function is orders of magnitude less than memory required for a directory of all card numbers.
In the field of digital compression, vector quantization is a coding technique which reduces the amount of data required to represent information such as a digitized sound or image. For vector quantization, a series or array of digital values is partitioned into subsets referred to as vectors. Each vector has components which are values from the series or array. For encoding, a vector is replaced by an index indicating a codevector which most closely matches the vector. Replacing vectors with indices compresses the series or array to fewer digital values. The information is decoded by replacing the indices with codevectors from the codebook.
An example use of vector quantization is in image coding. A digitized image represented by a two-dimensional array of values can be partitioned into image vectors, wherein each image vector is a set of sixteen 8-bit values which represents the intensities of pixels in a 4-by-4 block of pixels. Representing such image vectors without coding requires sixteen bytes of information per image vector. When encoding an image, each image vector is compared to every codevector in a codebook to find a best match. If the codebook contains 256 codevectors, a one-byte index which identifies the best match codevector replaces a 16-byte image vector. This provides a 16-to-1 reduction in the amount of information that must be stored or transmitted to represent the image.
A problem with vector quantization is the relatively long encoding time required to find the best codevector for each image vector in an image. In many applications, such as videophones, vectors must be quantized in real time as images and sounds are generated. Consequently, a number of techniques have been proposed to reduce the encoding time which include tree-structured vector quantization, finite-state vector quantization, and cache vector quantization. Still, fast processes are needed for vector quantization to facilitate real time encoding in systems such as videophones.